#include <bits/stdc++.h>
using namespace std;
//dp

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int size = nums.size();
        int *dp = new int[size]{0};
        dp[0] = nums[0];
        int ans = dp[0];
        for(int i=1; i<size; ++i){
            dp[i] = max(nums[i], dp[i-1]+nums[i]);
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

int main(){

}